package hanjia;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/14-下午2:05
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode131 {

//    //保持前几题一贯的格式， initialization
//    List<List<String>> res = new ArrayList<>();
//    List<String> cur = new ArrayList<>();
//
//    public List<List<String>> partition(String s) {
//        backtracking(s, 0, new StringBuilder());
//        return res;
//    }
//
//    private void backtracking(String s, int start, StringBuilder sb) {
//        //因为是起始位置一个一个加的，所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文，所以cur是满足条件的
//        if (start == s.length()) {
//            //注意创建一个新的copy
//            res.add(new ArrayList<>(cur));
//            return;
//        }
//        //像前两题一样从前往后搜索，如果发现回文，进入backtracking,起始位置后移一位，循环结束照例移除cur的末位
//        for (int i = start; i < s.length(); i++) {
//            sb.append(s.charAt(i));
//            if (check(sb)) {
//                cur.add(sb.toString());
//                backtracking(s, i + 1, new StringBuilder());
//                cur.remove(cur.size() - 1);
//            }
//        }
//    }
//
//    //helper method, 检查是否是回文
//    private boolean check(StringBuilder sb) {
//        for (int i = 0; i < sb.length() / 2; i++) {
//            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) {
//                return false;
//            }
//        }
//        return true;
//    }

//    public static void main(String[] args) {
//        String s="aab";
//        LeetCode131 leetCode131 = new LeetCode131();
//        leetCode131.partition(s);
//    }


    public List<List<String>> partition(String s) {

        List<String> result = new ArrayList<>();
        List<List<String>> results = new ArrayList<>();
        int start = 0;
        backtracking(start, s, result, results, new StringBuffer());
        return results;

    }

    private void backtracking(int start, String s, List<String> result, List<List<String>> results, StringBuffer sb) {

        if (start>=s.length()){
            results.add(new ArrayList<>(result));
            return;
        }


        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (isHuiWen(sb.toString())){
                result.add(sb.toString());
                backtracking(i+1,s,result,results,new StringBuffer());
                result.remove(result.size()-1);

            }

        }

    }


    private Boolean isHuiWen(String s) {
        int left = 0;
        int right = s.length()-1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;

        }
        return true;


    }


}
